"""
https://leetcode.cn/problems/two-sum/

1. 两数之和
简单
相关标签
相关企业
提示
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

 

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]
 

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
 

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

"""

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 先排序(创建一个元组的列表，第一个元素是值，第二个元素是当前索引)
        new_nums=[(v,i) for i,v in enumerate(nums)]
        # 对new_nums进行排序，排序规则是根据每个元组的第一个值，从小到大
        new_nums.sort(key=lambda x: x[0])

        # 从头和尾各自进行遍历，获取要求的和
        left=0
        right=len(new_nums)-1
        while left<right:
            sum=new_nums[left][0]+new_nums[right][0]
            if sum>target:
                right-=1
            elif sum<target:
                left+=1
            else:
                return [new_nums[left][1],new_nums[right][1]]

        

if __name__ == "__main__":
    solution = Solution()
    nums = [2,7,11,15]
    target = 9
    print(solution.twoSum(nums, target))